剑指offer 16——数值的整数次方

这道题可以利用二进制，就可以快速解决了。

原题

实现函数double Power(double base, int exponent)，求base的exponent次方。不得使用库函数，同时不需要考虑大数问题。

示例 1：

1 2	输入: 2.00000, 10 输出: 1024.00000

示例 2:

1 2	输入: 2.10000, 3 输出: 9.26100

示例 3:

1
2
3

输入: 2.00000, -2
输出: 0.25000
解释: 2-2 = 1/2^2 = 1/4 = 0.25

说明：

-100.0 < x < 100.0
n 是 32 位有符号整数，其数值范围是 [−2^31, 2^31 − 1] 。

原题url：https://leetcode-cn.com/problems/shu-zhi-de-zheng-shu-ci-fang-lcof/

解题

这道题，如果你是用正常计算的话，提交之后会发现报超时，因此，肯定需要寻找捷径的。

因为不能使用库函数，而且上面普通方法也是会超时的，那么问题的关键就是在如何快速计算。

而如果想快的，最好的办法就是可以利用曾经计算的结果，避免重复计算。

我一开始的想法是，比如计算 2^6 ，从数学上来说，等同于计算 4^3。但如果要用这种逻辑的话，就必须要求传入参数 n 是 2^w（其中 w 是正整数），否则计算逻辑会比较复杂。因此放弃该方案。

二进制

重点依旧是放在利用曾经计算的结果，避免重复计算上，那么理想情况也就是计算 x^n 后，之后希望直接计算 x^2n，而x^2n = x^n * x^n = x^(n + n)。

从上面的讨论可以看出，计算幂，可以转换成将指数进行合理的加法拆分。所谓合理，就是后一个是前一个的 2 倍，这样的话，就自然联想到要对指数从十进制转为二进制。

1 2	7 = (111) = 1 * 2^2 + 1 * 2^1 + 1 * 2^0 9 = (1001) = 1 * 2^3 + 0 * 2^2 + 0 * 2^1 + 1 * 2^0

当然，上面是从大到小累加，实际计算时肯定是从小到大进行累加的。

说到二进制，肯定少不了位运算，那么计算每一位二进制上的值，有什么快速的方法呢？

有的，利用n & 1，求出最低位的值（0或者1），然后n >> 1，右移，相当于移除最低位，不停循环，也就能计算出二进制上每一位的值了。

接下来看看代码：

class Solution {
    public double myPow(double x, int n) {
        if (x == 0) {
            return 0;
        }

        // 此处用long，是防止n是Integer.MIN_VALUE时，取反后直接就超过了Integer.MAX_VALUE
        long b = n;
        double res = 1.0;
        if(b < 0) {
            x = 1 / x;
            b = -b;
        }

        while(b > 0) {
            if ((b & 1) == 1) {
                res *= x;
            }
            // 底数扩大
            x *= x;
            // 指数右移
            b >>= 1;
        }
        return res;
    }
}